package cn.aylog.singleLinkList;

import com.sun.xml.internal.ws.wsdl.writer.document.soap.Body;

/**
 * 约瑟夫环问题
 *  使用环形链表解决
 * 描述:
 *  n个人围成一圈,从第k个人从1开始报数,当报出的数字为k时淘汰,下一个人重新从1开始报数,问淘汰顺序?
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleLink link = new CircleLink();
        link.createCircleBoys(15);
        link.show();
        System.out.println("开始游戏");
        link.play(2);
    }
}

class CircleLink {
    private Boy start = null; // 指向第一个节点

    /**
     * 根据传入的参数创建约瑟夫环
     */
    public void createCircleBoys(int num) {
        // 值的有效性判断
        if(num <= 0) {
            return;
        }
        Boy end = null; // 执行最后一个节点
        for(int i=1; i<=num; i++) {
            Boy boy = new Boy(i);
            if(i == 1) {
                start = boy;
                start.setNext(start);
                end = start;
            } else {
                end.setNext(boy);
                boy.setNext(start);
                end = boy;
            }
        }
    }

    /**
     * 开始解答约瑟夫环问题
     */
    public void play(int n) {
        // 空值判断
        if(start == null) {
            return;
        }
        Boy cur = start;
        Boy pre = start.getNext();
        // 获取pre节点
        while(pre.getNext() != cur) {
            pre = pre.getNext();
        }
        int cnt = 1;
        String ret = "";
        while (cur.getNext() != cur) {
            System.out.printf("%d -> %d\n", cnt, cur.getNo());
            if(cnt == n) {
                cnt = 1;
                System.out.println(cur.getNo());
                ret += cur.getNo() + " -> ";
                // out
                pre.setNext(cur.getNext());
                cur = pre.getNext();
            } else {
                cnt++;
                pre = cur;
                cur = cur.getNext();
            }
        }
        // 输出最后一个
        System.out.println(cur.getNo());
        ret += cur.getNo();
        System.out.println(ret);
    }

    /**
     * 链表打印
     */
    public void show() {
        // 空值判断
        if(start == null) {
            return;
        }
        Boy cur = start;
        do {
            System.out.println(cur.getNo());
            cur = cur.getNext();
        } while(cur != start);
    }
}

class Boy {
    private int no; // 标记
    private Boy next; // 指向下一个节点

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}
